package algorithm.dongtaiguihua;

import org.junit.Test;

public class BeiBao {

    @Test
    public void test() {
        //https://blog.csdn.net/qq_16234613/article/details/52235082

        int[] w = {5, 4, 7, 2, 6};
        int[] value = {12, 3, 10, 3, 6};

        int bag = 15;

        int[][] dp = new int[w.length][bag + 1];

        //初始化 矩阵第一排
        for (int j = 0; j < bag + 1; j++) {
            dp[0][j] = w[0] <= j ? value[0] : 0;
        }

        for (int i = 1; i < value.length; i++) {
            for (int j = 0; j < bag + 1; j++) {
                if (j < w[i]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + value[i]);

                System.out.println(String.format(" i %s j %s v %s", i, j, dp[i][j]));

            }
        }
        System.out.println(dp[w.length - 1][bag]);
    }


    /**
     * 20240201  01背包问题
     */
    @Test
    public void test2() {
        int[] w = {5, 4, 7, 2, 6};
        int[] v = {12, 3, 10, 3, 6};

        int bag = 15;

        // 先横向遍历,再向下遍历,所以物品放在一维,背包最大重量放到二维()
        int[][] dp = new int[v.length][bag + 1];

        // 初始化第一个物品
        for (int i = 0; i <= bag; i++) {
            dp[0][i] = w[0] > i ? 0 : v[0];
        }

        // 从第一个物品开始遍历
        for (int i = 1; i < v.length; i++) {
            System.out.print(i + " -> ");
            for (int j = 0; j <= bag; j++) {
                if (w[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
                System.out.print(dp[i][j] + " , ");
            }
            System.out.println();
        }
        System.out.println(dp[v.length - 1][bag]);
    }

    /**
     * 20240218 01背包 求组合个数问题
     */
    @Test
    public void test201(){
        int[] v = {5, 6, 3};
        int bag = 15;

        int [][]dp = new int[v.length][bag+1];
//        for (int i = 0; i < bag + 1; i++) {
//
//        }
        dp[0][v[0]] = 1;

        for (int i = 1; i < v.length; i++) {
            for (int j = 0; j < bag + 1; j++) {
                if(j>=v[i]) {
                    //有i 或者 没有i 的两种组合;
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i]] ;
                }
                else
                    dp[i][j] = dp[i-1][j];
            }
        }

//        for (int i = 0; i < dp.length; i++) {
//            for (int j = 0; j < dp[i].length; j++) {
//                System.out.print("" + dp[i][j] + "," );
//            }
//            System.out.println();
//        }

    }

    /**
     * 20240201 使用一维数组
     */
    @Test
    public void test4() {
        int[] w = {5, 4, 7, 2, 6};
        int[] v = {12, 3, 10, 3, 6};

        int bag = 15;
        /*
         * dp 是一个滚动数组,用来模拟二维数组
         */
        int dp[] = new int[bag + 1];
        for (int i = 0; i < v.length; i++) {
            System.out.print(i + " -> ");
            //必须 倒着遍历,防止物品重复放入背包
            for (int j = bag; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j - w[i]] + v[i], dp[j]);
                System.out.print(dp[j] + ", ");
            }
            System.out.println();
        }
        System.out.println(dp[bag]);
    }



    /**
     * 20240206 完全背包
     */
    @Test
    public void test0501() {
        //
        int[] w = {5, 4, 7, 2, 6};
        int[] value = {12, 3, 10, 3, 6};

        int bag = 15;

        // 定义：前i个物品,背包为j容量时,背包的最大价值。
        int dp[][] = new int[value.length][bag + 1];

        //int
        for (int i = 0; i < dp[0].length; i++) {
            // 错误: 要注意可以重复放入
            // if (i >= w[0]) dp[0][i] = value[0];
            // 从这个地方 +value[0] 可以体会到 这个是可重复放入的
            if (i >= w[0]) dp[0][i] = dp[0][i - w[0]]+value[0];
        }

        for (int i = 1; i < value.length; i++) {
            for (int j = 0; j <= bag; j++) {
                if (j >= w[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w[i]] + value[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[value.length - 1][bag]);
    }


    /**
     * 完全背包
     */
    @Test
    public void test502() {

        int[] w = {5, 4, 7, 2, 6};
        int[] v = {12, 3, 10, 3, 6};

        int bag = 15;

        int dp[][] = new int[v.length][bag + 1];

        System.out.print("i ->  ");
        //init
        for (int j = 0; j < dp[0].length; j++) {
            if (w[0] <= j) {
                dp[0][j] = dp[0][j - w[0]] + v[0];
                System.out.print(dp[0][j] + ", ");
            }
        }
        System.out.println();

        for (int i = 1; i < v.length; i++) {
            System.out.print("i ->" + i);
            //必须正序遍历背包,实现物品重复拿取
            for (int j = 0; j < bag + 1; j++) {
                if (j >= w[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
                System.out.print(" " + dp[i][j] + ", ");
            }
            System.out.println();
        }

        System.out.println(dp[v.length - 1][bag]);

    }

    /**
     * 20240206 完全背包  一维数组实现
     */
    @Test
    public void test6() {

        int[] w = {5, 4, 7, 2, 6};
        int[] v = {12, 3, 10, 3, 6};

        int bag = 15;

        //一维滚动数组
        int dp[] = new int[bag + 1];

        for (int i = 0; i < v.length; i++) {
            //必须正序遍历,实现物品重复放入
            for (int j = 0; j < bag + 1; j++) {
                if (j >= w[i]) dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        System.out.println(dp[bag]);
    }

    /**
     * 20240218 完全背包 求组合个数问题
     * 兑换零钱
     */
    @Test
    public void test7(){
        int[] v = {1, 2, 5};
        int bag = 5;

        int [][]dp = new int[v.length][bag+1];

        for (int j = 0; j < bag + 1; j++) {
//            for (int k = 0; k * v[0] <= j; k++) {
//                dp[0][j] =
//            }
            if(j%v[0] == 0){
//                dp[0][j] = j/v[0];
                // error
                dp[0][j] = 1;
            }
        }

        for (int i = 1; i < v.length; i++) {
            for (int j = 0; j < bag + 1; j++) {
                //当放入k个i物品时,dp[i][j] 的组合个数 就可k个物品的总和。
                for (int k = 0; k <= j / v[i]; k++) {
                    dp[i][j] += dp[i - 1][j - v[i] * k];
                }
            }
        }

//        for (int i = 0; i < dp.length; i++) {
//            for (int j = 0; j < dp[i].length; j++) {
//                System.out.print("" + dp[i][j] + "," );
//            }
//            System.out.println();
//        }

    }


}
